package main

import "fmt"

/*
----------插入排序---------
思路： 			9,5,66,1,21,42
1. 从第二个开始，向前插入到合适位置    				5,9,		66,1,21,42
2. 接着从第三个开始，向前插入到合适位置				5,9,66,		1,21,42
3. 接着从第四个开始，向前插入到合适位置				1,5,9,66,	21,42
4. 依次类推到最后一个完成

优点：可以边读边插入排序

平均时间复杂度：O(N^2)
最坏时间复杂度：O(N^2)
空间复杂度: O(1)
稳定性：稳定

*/

func main() {
	arr := []int{9,5,66,1,21,42}
	fmt.Println(insertSort(arr))
}

/*
先理解一个值的插入
把下标为 idx 的值向前插入到合适的位置
 */
func simpleInsert(arr []int,idx int){
	// 插入排序步长为 1
	gap := 1
	// backup 为备份要向前插入的值，j 为前一个值
	backup,j := arr[idx],idx - gap

	for j >= 0 && arr[j] > backup{
		// 把值往后移动
		arr[j+gap] = arr[j]
		j = j - gap
	}

	// 把值放到合适的位置
	arr[j+gap] = backup
}

func insertSort(arr []int) []int {
	length := len(arr)
	if length <= 1 {
		return arr
	}

	for i := 1;i < length; i++{
		// 也可以直接把 simpleInsert 函数直接复制过来，而不调用
		simpleInsert(arr,i)
	}

	return arr
}
